import java.util.*;

/**
 * @author LKQ
 * @date 2022/7/2 11:55
 * @description 动态规划
 */
public class Solution {
    public static void main(String[] args) {
        Solution solution = new Solution();
        int[][] stations =  {{10, 60}, {20, 30}, {30, 30}, {60, 40}};
        solution.minRefuelStops(100, 10, stations);
    }
    public int minRefuelStops(int target, int startFuel, int[][] stations) {
        int n = stations.length;
        // 定义dp[i] 加油i次的最大行驶英里数
        long[] dp = new long[n + 1];
        dp[0] = startFuel;
        for (int i = 0; i < n; i++) {
            for (int j = i; j >= 0; j--) {
                // 如果dp[j]能行驶到当前加油站，那么下一次行驶的最大距离为，从大到小遍历
                if (dp[j] >= stations[i][0]) {
                    dp[j + 1] = Math.max(dp[j + 1], dp[j] + stations[i][1]);
                }
            }
        }
        // 寻找超过target的最小下标
        for (int i = 0; i <= n; i++) {
            if (dp[i] >= target) {
                return i;
            }
        }
        return -1;
    }
}
